//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    //方式右下角最大边长
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int ans = 0;
        vector<vector<int>> dp(m,vector<int>(n));
        //初始化状态数组
        //第一列
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0]=='1'){
                dp[i][0] = 1;
                ans =1;
            }
        }
        //第一行
        for (int i = 0; i < n; ++i) {
            if (matrix[0][i]=='1'){
                dp[0][i] = 1;
                ans =1;
            }
        }
        //行的长度和列的长度都增加1， 有利于边界条件的处理
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j]=='1'){
                    dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1]))+1;
                    ans = max(ans, dp[i][j]);
                }
            }

        }
        return ans*ans;
    }
};